This invention relates generally to block floating point arithmetic such as used in the butterfly operation of the decimation in time algorithm used in Fast Fourier Transforms (FFT), and more particularly the invention relates to circuitry for use in implementing block floating point arithmetic.
The Fourier transform arises in a variety of situations in science and engineering and is one of the most widely used and studied mathematical transform techniques. The Fast Fourier Transform, or FFT is well adapted to the very rapid calculation of Fourier transforms on digital systems.
A Fourier series is used to perform a spectral analysis. The function being analyzed is represented as the sum of a series of sine and cosine waves of appropriate frequencies and appropriate amplitudes. By noting the frequencies used in the representation, a spectral analysis of the original signal results directly.
According to a well-known relationship, convolutions in the time domain can be implemented as vector multiplications of the frequency representations of the input signals in the transformed (frequency) domain. This fact allows the rapid implementation of filters through the convolution of the filter sequence with the data sequence in the frequency domain; the method is generally referred to as fast convolution and is one of the most important areas in which signal engineers use Fourier transforms and FFTs in particular. The Fourier transform is also the gateway to other widely used transforms such as the cosine transform.
Rabiner and Gold, Theory and Application of Digital Signal Processing, Prentice Hall, 1975 discusses spectrum analysis and the fast Fourier transform. As described therein a basic operation of the decimation in time algorithm used in FFT is the so-called Butterfly in which two complex number inputs, A and B, are combined with a weighting factor, W, to give the two outputs X and Y via the operation ##EQU1## Applicant's copending application Ser. No. 904,421 filed Sept. 8, 1986, is directed to circuitry for expeditiously performing the Butterfly operations on a plurality of sets of complex data. A Pipelined mode of operation is employed whereby several sets of data are operated on concurrently and two inputs are entered and two outputs are generated every four cycles.
Each Butterfly computation in the FFT involves multiplication of two complex numbers and another addition/subtraction of complex numbers. All together the operation involves addition of three numbers, which may cause an overflow of up to two bits. Partial prevention of such an overflow can be achieved by automatically shifting the results of each pass 1 bit to the right (divide by 2), but that does not prevent overflow in the rare case of 2-bit overflow--when both inputs to the Butterfly equal 1 and the angle of rotation is anywhere between 0 and 90 degrees. On the other hand, it may reduce the working dynamic range substantially--when actually there were no overflows, and the shifting was performed unnecessarily. Another way of handling the overflow problem is by scaling (shifting) the pass results by the required number of bits so as to prevent overflow, only when an overflow occurs in any of the computed Butterflies in that pass. This way, the scaling is done only when necessary, retaining maximum precision throughout the whole operation, and the number of shifts is according to the actual number of overflow bits--giving complete protection against losing information on account of the overflow. This second method is often referred to as Block Floating Point Arithmetic.
Using Block Floating Arithmetic for FFT computation means that different blocks of processed data may have different scale factors associated with them (the scale factor is the total number of right shifts carried out during one FFT instruction execution). For instance, when computing 2-D FFTs, the FFT of each row (or a number of rows in cases where row size allows multiple simultaneous FFTs) may be computed by one FFT operation with its associated scale factor. When more than one FFT operation is required for computation of all the row FFTs, the data in each column in the resultant image is associated with several scale factors. Therefore, prior to computation of the column FFTs the data in each column needs to be aligned (alignment of the binary point, if the scale factors are regarded as exponents). The alignment should be according to the maximum scale factor associated with any of the involved data.